Chuỗi bậc
Giao diện
Bài viết này cần thêm liên kết tới các bài bách khoa khác để trở thành một phần của bách khoa toàn thư trực tuyến Wikipedia. (tháng 7 2018) |
Bài viết này cần thêm chú thích nguồn gốc để kiểm chứng thông tin. |
Chuỗi bậc trong lý thuyết đồ thị là danh sách bậc của các đỉnh thuộc đồ thị. Với đồ thị G và n đỉnh, chuỗi bậc của đồ thị là dãy (d1, d2,..., dn), trong đó di (i=1, 2,..., n) là bậc của đỉnh i thuộc đồ thị G.
Hai đồ thị đẳng cấu có chuỗi bậc giống nhau; ngược lại hai đồ thị có chuỗi bậc giống nhau không nhất thiết là hai đồ thị đẳng cấu.
Định lý về chuỗi bậc[sửa | sửa mã nguồn]
Với mọi dãy số D = (d1 ≤ d2 ≤... ≤ dn) và D' = (d'1 ≤ d'2 ≤... ≤ d'n) thoả mãn:
ta có D là chuỗi bậc của đồ thị, khi D' cũng là chuỗi bậc của đồ thị.
Nguồn tham khảo[sửa | sửa mã nguồn]
Degree Sequence (Trang viết bằng tiếng Anh).